package com.topInterview;

/**
 * 缺失的第一个正数
 *
 * @Author: huangzhigao
 * @Date: 2022/2/19 18:10
 */
public class Leecode41_missFirstNum {
    public int firstMissingPositive(int[] nums) {
        int left = 0;
        int right = nums.length;
        while (left < right) {

            if(nums[left] == left+1){
                left++;
            }else if(nums[left] <= left || nums[left] > right || nums[left] == nums[nums[left]-1]){
                nums[left] = nums[--right];
            }else {
                swap(nums, left, nums[left] - 1);
            }



//            if (nums[left] > right || nums[left] <= left || nums[left] == nums[nums[left] - 1]) {
//                nums[left] = nums[--right];
//            } else if (nums[left] == left + 1) {
//                left++;
//            } else {
//
//            }
        }
        return left + 1;


    }


    public void swap(int[] nums, int l, int r) {
        int num = nums[l];
        nums[l] = nums[r];
        nums[r] = num;
    }

    public static void main(String[] args) {
        Leecode41_missFirstNum s = new Leecode41_missFirstNum();
        s.firstMissingPositive(new int[]{1, 2, 0});
    }
}
